package leetcode;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/19 16:17
 */
public class SegmentTree2<E> {
    private E[] tree;
    private E[] data;
    private Merger<E> merger;


    public SegmentTree2(E[] arr, Merger<E> merger){
        this.merger = merger;
        data = (E[])new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }


        tree = (E[]) new Object[4 * arr.length];
        buildSegmentTree(0,0,data.length-1);

    }



    public int getSize(){
        return data.length;
    }

    public E get(int index){
        if(index<0 || index >= data.length){
            throw  new IllegalArgumentException("Index is illegal.");
        }
        return data[index];
    }

    private int leftChild(int index){
        return 2*index + 1;
    }

    private int rightChild(int index){
        return 2*index +2;
    }


    /**
     *  在treeIndex的位置创建[left ...right]的线段树
     * @param treeIndex 线段树的根
     * @param left   左线段
     * @param right   右线段
     *                递归实现
     */
    private void buildSegmentTree(int treeIndex, int left, int right ) {

        if(left == right){
            tree[treeIndex] = data[left];
            return;
        }

        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);

        int mid = left +(right - left)/2;

//        然后再基于2个区间创建线段树
        buildSegmentTree( leftTreeIndex,left,mid);
        buildSegmentTree( rightTreeIndex,mid+1,right);

        //可以根据实际的业务去书写---需要去实现一个接口
        tree[treeIndex] =  merger.merge(tree[leftTreeIndex] , tree[rightTreeIndex]) ;
    }


    //返回区间[queryL,queryR]的值
    public E query(int queryL,int queryR){
        if(queryL < 0 || queryL >= data.length ||
                queryR < 0 || queryR >= data.length || queryL > queryR){

            throw  new IllegalArgumentException("Index is illegal.");
        }

        return query(0,0,data.length-1,queryL,queryR);
    }
    //在以treeID为根的线段树中[left...right]的范围里，搜索区间[queryL...queryR]的值
    private E query(int treeIndex, int left, int right, int queryL, int queryR) {
        if(left == queryL && right==queryR){
            return tree[treeIndex];
        }
        int mid = left + (right- left)/2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);

        if(queryL>= mid+1){
            return query(rightTreeIndex,mid+1,right,queryL,queryR);
        }else if( queryR <= mid){
            return query(leftTreeIndex,left,mid,queryL,queryR);
        }

        //说明要查询的在中间，两边都要查找
        E leftRes = query(leftTreeIndex,left,mid,queryL,mid);
        E rightRes = query(rightTreeIndex,mid+1,right,mid+1,queryR);

        return  merger.merge(leftRes,rightRes);//根据实际业务操作


    }


    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append('[');
        for (int i = 0; i < tree.length; i++) {
            if(tree[i] !=null){
                res.append(tree[i]);
            }else{
                res.append("null");
            }

            if(i != tree.length - 1){
                res.append(", ");
            }
        }
        res.append(']');
        return res.toString();
    }
}
